/*
 * @Author: wwssaabb
 * @Date: 2021-12-15 15:42:55
 * @LastEditTime: 2021-12-15 16:00:51
 * @FilePath: \handwritten-code\排序算法\冒泡排序.js
 */

/* 
  冒泡排序，时间复杂度O(n**2)
  主要思路是通过两两比较，大的数向右移，小的向左移，第一次遍历时完成最大值的排序，n-1次时完成从大到小的排序
*/


console.time(1)

function bubbleSort(arr) {
  let len = arr.length
  for (let i = 0; i < len - 1; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        //左边的值大于右边，两值交换
        //位运算的异或运算实现两数交换
        // arr[j] ^= arr[j + 1]
        // arr[j + 1] ^= arr[j]
        // arr[j] ^= arr[j + 1]
        //也可以使用第三个变量来进行交换
        let temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
      }
    }
  }
  return arr
}

const arr = [89, 58, 66, 74, 15, 34, 99, 78, 45, 33, 21, 16, 85, 54]

console.log(bubbleSort(arr))

console.timeEnd(1)